<!--
 * @Date: 2022-01-05 22:02:32
 * @LastEditTime: 2022-06-26 07:40:12
-->

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      // 节点
      class Node {
        constructor(val, next) {
          this.val = val;
          this.next = next;
        }
      }

      // 链表类
      class LinkList {
        constructor() {
          this.size = 0;
          this.initNode = new Node(null, null);
        }

        // 检查节点是否超出范围
        _checkIndex(index) {
          if (index > this.size || index < 0) throw new Error("超出链表范围");
        }

        // 查找上一个节点
        // header - 从头结点开始查找
        // targetIndex - 目标节点index
        // currentIndex - 游标
        _find(header, targetIndex, currentIndex) {
          // 退出条件
          if (targetIndex === currentIndex) {
            return header;
          }

          // header.next - 节点往下
          return this._find(header.next, targetIndex, currentIndex + 1);
        }

        // 插入节点 要在index的位置插入val
        insertNode(val, index) {
          // 检查index是否存在
          this._checkIndex(index);
          // 0-1-2-3要在2位置插入节点，找到1;把1的next改为新的Node，这个Node值就是val，next就是prev.next,他之前的next
          let prev = this._find(this.initNode, index, 0);
          prev.next = new Node(val, prev.next);
          this.size++;
          return prev.next;
        }

        // 删除节点
        removeNode(index) {
          // 检查index是否存在
          this._checkIndex(index);
          // 找到上一个节点
          let prev = this._find(this.initNode, index, 0);
          // 找到删除之前的当前节点
          let node = prev.next;
          // 修改上一个节点的next
          prev.next = node.next;
          // 修改当前节点的next
          node.next = null;
          this.size--;
          return node;
        }

        // 查节点
        getNode(index) {
          // 判空
          if (this.isEmpty()) return;
          // 是否存在
          this._checkIndex(index);

          // 找到上一个节点
          let prev = this._find(this.initNode, index, 0);
          // 返回下一个节点
          return prev.next;
        }

        // 是否为空
        isEmpty() {
          return this.size === 0;
        }

        // 链表的长度
        getSize() {
          return this.size;
        }
      }
      const li = new LinkList();
      li.insertNode(4, 0);
      li.insertNode(3, 1);
      li.insertNode(2, 2);
      li.insertNode(1, 3);
      /* 
            时间O(n)
            空间O(1)
        */

      // 找到链表的中间节点
      var middleNode = function (head) {
        
      };
      // 合并两个有序链表
      var copyRandomList = function(head) {
          // 解题思路：链表相加

          let head2 = new LinkList()
      };
      console.log(copyRandomList(li.getNode(0)), "swapPairs(li, li2)");
    </script>
  </body>
</html>
